package leetcode_401_500;

import java.util.ArrayList;
import java.util.List;

public class LeeCode_438 {
    public static void main(String[] args) {
        System.out.println(findAnagrams("cbaebabacd", "abc"));
    }
    private static List<Integer> findAnagrams(String s, String p) {
        int n = s.length();
        int[][] table = new int[26][n + 1];
        for (int i = 0; i < n; i++) {
            int index = s.charAt(i) - 'a';
            for (int j = 0; j < 26; j++) {
                table[j][i + 1] = table[j][i];
            }
            table[index][i + 1]++;
        }
        int[] goal = new int[26];
        for (int i = 0; i < p.length(); i++) {
            int index = p.charAt(i) - 'a';
            goal[index]++;
        }
        int l = 0, r = l + p.length();
        List<Integer> ans = new ArrayList<>();
        while (r <= n){
            boolean flag = true;
            for (int i = 0; i < 26; i++) {
                if (table[i][r] - table[i][l] != goal[i]){
                    flag = false;
                    break;
                }
            }
            if (flag){
                ans.add(l);
            }
            l++;
            r++;
        }
        return ans;
    }
}
